#include <cstdlib>
#include <cstdint>
#include <stdlib.h>
#include <iostream>
#include <random>
#include <chrono>
#include <immintrin.h>

long long int getcycle()
{
    uint64_t low, high;
    __asm volatile("rdtsc" : "=a"(low), "=d"(high));
    return (high << 32) | low;
}

bool check_func(float num, float num_2, char *charHas1_num)
{
    // std::random_device rd;
    // std::mt19937 gen(rd());

    bool result = true;
    float num1 = num - int(num);
    float num2 = num_2 - int(num_2);
    for (int i = 0; i < 16; ++i)
    {
        int ii = i % 4;
        int jj = i / 4;
        // if( ((ii+jj)-(ii/2+jj/2)) != int(charHas1_num[i]) )return false;
        if ((((i % 4) + (i / 4) - ((i % 4) / 2) - (i / 8))) != int(charHas1_num[i]))
            return false;
    }
    return true;
}

void generate()
{

    int a=0,b=0,c=0;
    int count=0;
    for(int i=0;i<=16;++i){
        for(int j=0;j<=16;++j){
            for(int k=0;k<=16;++k){
                for(int l=0;l<=16;++l){
                    if(i+j+k+l==16){
                        count++;
                        //printf("count=%d, i=%d,j=%d,k=%d,l=%d\n",count,i,j,k,l);
                    }
                }
            }
        }
    }
    //func_a_%d_b_%d_c_%d(){
    // unsigned char [a];
    //}


    std::random_device rd;
    std::mt19937 gen(rd());
    unsigned short num[16];//16*16=256;
    unsigned char count4bit_16[16] = {0};
    unsigned long long int ans[16] = {0}, ans2[16] = {0};
    for (int i = 0; i < 16; ++i)
        num[i] = gen() % 65536;
    // srand(time(NULL));
    unsigned char charHas1_num[256] = {0};    // 0-255的数，该数二进制中有多少个1。
    unsigned char char_1_index[256][8] = {0}; // 8*256;  记录每个char num中1的位置   2KB ,可压缩为一半空间，但是取数据时不好写
    unsigned char char_1_index_4bit[16][4] = {0};
    unsigned char count_char_1_sum[256] = {0};     // 记录每个数字中1的个数  0-8用4bit存 , 可压缩为一半空间128B
    unsigned char count_char_1_sum_4bit[16] = {0}; //
    for (int i = 0; i < (1 << 8); ++i)
    {
        int num = 0;
        int countIndex = 0;
        for (int j = 0; j < 8; ++j)
        {
            if (i & (1 << j))
            {
                num++;
                char_1_index[i][countIndex++] = j;
            }
        }
        count_char_1_sum[i] = countIndex;
        // if (i % 2 == 0)
        //     count_char_1_sum[i / 2] = countIndex;
        // else
        //     count_char_1_sum[i / 2] += countIndex * (1 << 4);

        charHas1_num[i] = num;
    }
    for (int i = 0; i < 16; ++i)
    {
        int num = 0;
        int countIndex = 0;
        for (int j = 0; j < 4; ++j)
        {
            if (i & (1 << j))
            {
                num++;
                char_1_index_4bit[i][countIndex++] = j;
            }
        }
        count_char_1_sum_4bit[i] = countIndex;
    }
    for (int i = 0; i < 16; ++i)
    {
        for (int j = 0; j < 16; j++)
        {
            // printf("i=%d, j=%d\n count_char_1_sum[%d]=%d",i,j,i*16+j,count_char_1_sum[i*16+j]);
            // printf("%d ",count_char_1_sum[i*16+j]);
            // printf("%d ",( (i%4) + (i/4) - ((i%4)/2) - (i/8) )  +  ( (j%4) + (j/4) - ((j%4)/2) - (j/8) ) );
        }
        // printf("\n");
    }
    // int is_found=0;
    // for(int i=0;i<(1<<30);++i){
    //     int rndnum=gen();
    //     int rndnum2=gen();
    //     float dnum=*(float*)(&rndnum);
    //     float dnum2=*(float*)(&rndnum2);
    //     if(check_func(rndnum,dnum2,count_char_1_sum)){
    //         printf("found i=%f,j=%f\n",dnum,dnum2);
    //         is_found=1;
    //         break;
    //     }
    // }
    // if(!is_found)printf("not found\n");

    unsigned char isExistRange0_255_1[32] = {0};
    for (int i = 0; i < 32; ++i)
    {
        isExistRange0_255_1[i] = gen() % 4;
    }

    unsigned char stroageEncounterNum_1[256] = {0};
    unsigned char EncounterNum_to_EncodeNum_1[256] = {0};
    int count1 = 0;

    auto time1 = std::chrono::system_clock::now();
    auto start1 = getcycle();
    // 第一种方案
    for (int I = 0; I < 8; ++I)
    {
        count1 = 0;
        for (int i = 0; i < 256; ++i)
        {
            // for (int j = 0; j < 8; ++j)
            {
                int tmp = ((isExistRange0_255_1[i / 8] >> (i % 8)) & 1);
                stroageEncounterNum_1[count1] = (i)*tmp;
                // EncounterNum_to_EncodeNum_1 [i] = count1 * tmp;
                count1 += tmp;
                // stroageEncounterNum_1[count1]
            }
        }
        // count1=0;
        for (int i = 0; i < count1; ++i)
        {
            // int tmp=((isExistRange0_255_1[ i/8 ] >> (i%8)) & 1);
            // stroageEncounterNum_1[count1]=i*tmp;
            // count1 += tmp;
            EncounterNum_to_EncodeNum_1[stroageEncounterNum_1[i]] = i;
        }
        // int sum=0;
        for (int i = 0; i < (1 << 20); ++i)
        {
            // int num=i%16;
            // count1+=( (num%4) + (num/4) - ((num%4)/2) - (num/8) );
            // count1+=charHas1_num[num];
        }
    }

    auto end1 = getcycle();
    auto time2 = std::chrono::system_clock::now();
    // 第二种方案
    unsigned char stroageEncounterNum_1_2[256] = {0};
    unsigned char EncounterNum_to_EncodeNum_1_2[256] = {0};
    unsigned char count1_2 = 0;

    for (int I = 0; I < 8; ++I)
    {
        count1_2 = 0;
        for (unsigned char ii = 0; ii < 32; ++ii)
        {
            // int not1_num = (count_char_1_sum[isExistRange0_255_1[i] / 2] >> (isExistRange0_255_1[i] & 1) * 4) & 0xf;
            unsigned char num = isExistRange0_255_1[ii];
            unsigned char not1_num = count_char_1_sum[num];
            // int num= (isExistRange0_255_1[ii/2]>>(4*(ii&1))) & 0xf;
            // int not1_num = count_char_1_sum_4bit[num];
            // int i=isExistRange0_255_1[ii]/16;
            // int j=isExistRange0_255_1[ii]%16;
            // int not1_num = ( (i%4) + (i/4) - ((i%4)/2) - (i/8) )  +  ( (j%4) + (j/4) - ((j%4)/2) - (j/8) );

            // not1_num = 0-8
            unsigned char offset = (unsigned char)(8) * ii;
            for (unsigned char j = 0; j < not1_num; ++j)
            {
                stroageEncounterNum_1_2[count1_2 + j] = char_1_index[num][j] + offset;
                // stroageEncounterNum_1_2[count1_2 + j] = char_1_index_4bit[num][j] + 4 * ii;
                // char_1_index_4bit[]
                EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + j]] = count1_2 + j;
            }
            // int j=0;
            // while(j<not1_num){
            //     stroageEncounterNum_1_2[count1_2 + j] = char_1_index[isExistRange0_255_1[i]][j] + 8 * i;
            //     EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + j]] = count1_2 + j;
            //     ++j;
            // }

            // switch(not1_num){
            //     case 0:
            //         break;
            //     case 1:
            //         stroageEncounterNum_1_2[count1_2 + 0] = char_1_index[isExistRange0_255_1[i]][0] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 0]] = count1_2 + 0;
            //         break;
            //     case 2:
            //         stroageEncounterNum_1_2[count1_2 + 0] = char_1_index[isExistRange0_255_1[i]][0] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 0]] = count1_2 + 0;
            //         stroageEncounterNum_1_2[count1_2 + 1] = char_1_index[isExistRange0_255_1[i]][1] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 1]] = count1_2 + 1;
            //         break;
            //     case 3:
            //         stroageEncounterNum_1_2[count1_2 + 0] = char_1_index[isExistRange0_255_1[i]][0] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 0]] = count1_2 + 0;
            //         stroageEncounterNum_1_2[count1_2 + 1] = char_1_index[isExistRange0_255_1[i]][1] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 1]] = count1_2 + 1;
            //         stroageEncounterNum_1_2[count1_2 + 2] = char_1_index[isExistRange0_255_1[i]][2] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 2]] = count1_2 + 2;
            //         break;
            //     case 4:
            //         stroageEncounterNum_1_2[count1_2 + 0] = char_1_index[isExistRange0_255_1[i]][0] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 0]] = count1_2 + 0;
            //         stroageEncounterNum_1_2[count1_2 + 1] = char_1_index[isExistRange0_255_1[i]][1] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 1]] = count1_2 + 1;
            //         stroageEncounterNum_1_2[count1_2 + 2] = char_1_index[isExistRange0_255_1[i]][2] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 2]] = count1_2 + 2;
            //         stroageEncounterNum_1_2[count1_2 + 3] = char_1_index[isExistRange0_255_1[i]][3] + 8 * i;
            //         EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[count1_2 + 3]] = count1_2 + 3;
            //         break;
            // }

            count1_2 += not1_num;
        }
        for (int i = 0; i < count1_2; i++)
        {
            // EncounterNum_to_EncodeNum_1_2[stroageEncounterNum_1_2[i]] = i;
        }
    }
    auto time3 = std::chrono::system_clock::now();
    printf("start cycle3\n");
    auto end2 = getcycle();
    __m256i num256i = _mm256_loadu_epi16(num);
    __m512i num512i_1 = _mm512_set1_epi64(0);
    __m512i num512i_2 = _mm512_set1_epi64(0);

    for(int i=0;i<16;++i){
        // tmp = (num256i >> j) & 1; //__m256i
        //num512i_1 |= (j<<(4*c))*tmp; 
    }


    for (int i = 0; i < 16; ++i)
    {
        unsigned char c = 0;
        unsigned long long int tmp_ans2=0;
        unsigned int tmp_ans2_1=0;
        unsigned int tmp_ans2_2=0;
        unsigned long long int tmp_ans1_1=0;
        unsigned int tmp_ans1_2=0;
        for (unsigned long long int j = 0; j < 16; ++j)
        {
            unsigned char tmp = ((num[i] >> j) & 1u); // 0 or 1
            // stroageEncounterNum_4bit_16[i][c] = j * tmp;
            //ans[i] |= ((j << (4 * c)) * tmp);
            //tmp_ans1_1 |=  ( (j << (4 * c)) * tmp);
            // tmp_ans |= ( (j*tmp)<<(4*c) );
            // EncounterNum_to_EncodeNum_4bit_16[i][j] = c;
            //ans2[i] = (ans2[i] << 4) + c;
            //tmp_ans2_1 = (tmp_ans2_1 << 4) + c;
            c += tmp;
        }
        // for (int j = 8; j < 16; ++j)
        // {
        //     unsigned char tmp = ((num[i] >> j) & 1); // 0 or 1
        //     // stroageEncounterNum_4bit_16[i][c] = j * tmp;
        //     //ans[i] |= ((j * tmp) << (4 * c));
        //     //ans[i] |= (((unsigned long long int)(j * tmp) << (4 * c)));
        //     tmp_ans1_2 |=  ( (j << (4 * c)) * tmp);
        //     // tmp_ans |= ( (j*tmp)<<(4*c) );
        //     // EncounterNum_to_EncodeNum_4bit_16[i][j] = c;
        //     //ans2[i] = (ans2[i] << 4) + c;
        //     tmp_ans2_2 = (tmp_ans2_2 << 4) + c;
        //     c += tmp;
        // }
        //ans2[i] = ((unsigned long long int)tmp_ans2_1<<32)+tmp_ans2_2;
        //ans[i] = ((unsigned long long int)tmp_ans1_1<<32)+tmp_ans1_2;

        //ans2[i]=tmp_ans2_1;
        // ans[i]=tmp_ans1_1 ;
        count4bit_16[i] = c;
    }
    unsigned long long int tmp_ans[16]={0};
    unsigned long long int tmp_ans2[16]={0};
    unsigned c0_15[16]={0};
    for(unsigned long long int j=0;j<16;++j){
        unsigned char tmp[16];
        // unsigned char tmp0 = ((num[0] >> j) & 1); // 0 or 1
        // unsigned char tmp1 = ((num[1] >> j) & 1); // 0 or 1
        // unsigned char tmp2 = ((num[2] >> j) & 1); // 0 or 1
        // unsigned char tmp3 = ((num[3] >> j) & 1); // 0 or 1
        // unsigned char tmp4 = ((num[4] >> j) & 1); // 0 or 1
        // unsigned char tmp5 = ((num[5] >> j) & 1); // 0 or 1
        // unsigned char tmp6 = ((num[6] >> j) & 1); // 0 or 1
        // unsigned char tmp7 = ((num[7] >> j) & 1); // 0 or 1
        // unsigned char tmp8 = ((num[8] >> j) & 1); // 0 or 1
        // unsigned char tmp9 = ((num[9] >> j) & 1); // 0 or 1
        // unsigned char tmp10 = ((num[10] >> j) & 1); // 0 or 1
        // unsigned char tmp11 = ((num[11] >> j) & 1); // 0 or 1
        // unsigned char tmp12 = ((num[12] >> j) & 1); // 0 or 1
        // unsigned char tmp13 = ((num[13] >> j) & 1); // 0 or 1
        // unsigned char tmp14 = ((num[14] >> j) & 1); // 0 or 1
        // unsigned char tmp15 = ((num[15] >> j) & 1); // 0 or 1
        for(int k = 0; k <16;k++){
            //tmp[k] = (num[k]>>j) & 1;
            //tmp_ans[k] |= ( (j << (4 * c0_15[k])) * tmp[k]);
            //tmp_ans2[k] = (tmp_ans2[k]<<4) + c0_15[k]; 
            //c0_15[k] += tmp[k];
        }
        for(int k = 0; k <16; k++){
            //tmp_ans[k] |= ( (j << (4 * c0_15[k])) * tmp[k]);
            //tmp_ans2[k] = (tmp_ans2[k]<<4) + c0_15[k];
        }
        for(int k = 0; k <16; k++){
            //c0_15[k] += tmp[k];
        }
    }

    auto end3 = getcycle();
#if 1
    printf("cycle 1 = %lld\n", end1 - start1);
    printf("cycle 2 = %lld\n", end2 - end1);
    printf("cycle 3 = %lld\n", end3 - end2);
    auto duration1 = std::chrono::duration_cast<std::chrono::nanoseconds>(time2 - time1).count();
    auto duration2 = std::chrono::duration_cast<std::chrono::nanoseconds>(time3 - time2).count();
    std::cout << "time1 ns : " << duration1 << " one number : " << 1.0 * duration1 / (1000) << std::endl;
    std::cout << "time1 ns : " << duration2 << " one number : " << 1.0 * duration2 / (1000) << std::endl;
    std::cout << "speed up:" << (double)duration1 / duration2 << std::endl;
    unsigned long long int sum=0;
    for(int i=0;i<16;++i){
        sum+=ans[i]+ans2[i]+count4bit_16[i]+tmp_ans[i]+tmp_ans2[i]+c0_15[i];
    }
    printf("sum=%lld\n",sum);

    if (count1 != count1_2)
    {
        printf("count error count1=%d, count1_2=%d\n", count1, count1_2);
    }
    else
    {
        printf("count success count=%d\n", count1);
    }
    for (int i = 0; i < 256; ++i)
    {
        if (stroageEncounterNum_1[i] != stroageEncounterNum_1_2[i])
        {
            printf("stroageEncounterNum_1[%d]=%d, stroageEncounterNum_1_2[%d]=%d\n",
                   i, stroageEncounterNum_1[i], i, stroageEncounterNum_1_2[i]);
        }
        if (EncounterNum_to_EncodeNum_1[i] != EncounterNum_to_EncodeNum_1_2[i])
        {
            printf("EncounterNum_to_EncodeNum_1[%d]=%d, EncounterNum_to_EncodeNum_1_2[%d]=%d\n",
                   i, EncounterNum_to_EncodeNum_1[i], i, EncounterNum_to_EncodeNum_1_2[i]);
        }
    }
#endif
}